package algorithmExample;

/**
 * @author: zhang.rongqing
 * @since: 2019/10/24
 */

//给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
//
//        请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
//
//        你可以假设 nums1 和 nums2 不会同时为空。
//        示例 1:
//        nums1 = [1, 3]
//        nums2 = [2]
//
//        则中位数是 2.0
//        示例 2:
//
//        nums1 = [1, 2]
//        nums2 = [3, 4]
//
//        则中位数是 (2 + 3)/2 = 2.5

public class MediumOfTwoSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int iLength = nums1.length;
        int jLength = nums2.length;
        //+1为了排除奇数的情况
        int imin = 0, imax = jLength, halfLen = (imin + imax + 1) / 2;
        ;
        //保证nums1长度大于nums2
        if (iLength < jLength) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }

        while (imin < imax) {
            int i = (imin + imax) / 2;
            int j = halfLen - i;
            if (i > imin && nums1[i] > nums2[j + 1]) {
                imax = i - 1;
            } else if (i < imax && nums2[j] > nums1[i + 1]) {
                imin = i + 1;
            } else {
                int maxLeft = 0;
                if (i == 0) {
                    maxLeft = nums2[j - 1];
                } else if (j == 0) {
                    maxLeft = nums1[i - 1];
                } else {
                    maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                if ((iLength + jLength) % 2 == 1) {
                    return maxLeft;
                }

                int minRight = 0;
                if (i == iLength) {
                    minRight = nums2[j];
                } else if (j == jLength) {
                    minRight = nums1[i];
                } else {
                    minRight = Math.min(nums2[j], nums1[i]);
                }

                return (maxLeft + minRight) / 2.0;

            }
        }
        return 0;
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 2};
        int[] nums2 = new int[]{3, 4};
        int[] num3 = new int[]{6};
        int[] num4 = new int[]{1, 2, 3};
        MediumOfTwoSortedArrays mediumOfTwoSortedArrays = new MediumOfTwoSortedArrays();
        System.out.println(String.format("the medium num:%s", mediumOfTwoSortedArrays.findMedianSortedArrays(nums1, nums2)));
    }
}
